从0打卡leetcode之day 5 ---两个排序数组的中位数
前言
我靠，才坚持了四天，就差点不想坚持了。不行啊，我得把leetcode上的题给刷完，不然怕是不好进入bat的大门。
题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 均不为空。
示例
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5``解题
最简单粗暴的就是把这两个数组头尾连接起来，然后重新给他们排序一下，冒泡排序相信你信手拈来，当然，你也可以装逼用快速排序。
但是，如果这样子做的话，题目给你的有序数组就没啥用了，和无序一个样，所以这样做是不行的。题目要求是时间复杂度不能超过O(log(n+m))，说实话，这个复杂度我是不知道怎么做好，我的做法时间复杂度是O(n+m)。
具体是这样的
居然两个数组都是有序的了，我们可以再弄一个中间数组，然后把两个数组各自从数组头开始比较，哪个元素小，我们就把它存在中间数组。然后接下下一个元素一直比较下去。
我还是直接上代码吧。如下：
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int t = m + n;//总长度
int temp[] = new int[t];
int i = 0, j = 0, k = 0;
double obj;//用来存目标值
while(i < m && j < n){
//把数组中比较小的值转移到temp数组中
if(nums1[i] < nums2[j]){
temp[k++] = nums1[i++];
}else{
temp[k++] = nums2[j++];
}
}
//把剩余的转移过去
while (i < m){
temp[k++] = nums1[i++];
}
while(j < n){
temp[k++] = nums2[j++];
}
//两个数组的总个数是奇数还是偶数
if(t % 2 == 0){//偶数
obj = (temp[t/2] + temp[(t-1)/2]) / 2.0;
}else{
obj = temp[t/2];
}
return obj;
}虽然时间复杂度是O(n+m)，但是提交的时候居然通过了，而且还打败了93%的人。
不过，这里还可以在优化，把时间复杂度降低到O((n+m)/2)。
就是说其实我们不用给整个temp数组排序，我们只要求出前面一半的数组元素就可以知道中间那个元素了，。例如不管一共是偶数个元素还是奇数个元素，我们让temp存到下标为t/2就可以了。然后再来判断t是奇数还是偶数…..
例如上面两个示例，示例1一共有三个元素，那么temp[t/2]=temp[1]=2。然后直接把temp[t/2]=temp[1]取出来返回就可以了。
示例2一共有4个元素，那么temp[t/2]=temp[2]=3。由于是偶数，我们直接把temp[t/2]=3和temp[t/2-1]=2这两个元素取出来处理之后返回就可以了。
至于代码这么写，我就不写了。知道有这么一回事就可以了。
如果你坚持想要O(log(n+m))的时间复杂度，那么可以看官方给的答案：
出问题了
完
往期:
从零打卡leetcode之day 4—无重复最长字符串
从零打卡leetcode之day 3—最大子序列
假如你有更好的做法，欢迎提出来让大家涨涨知识哦。由于该公众号没有留言功能，为了大家更好的交流，我创建了一个微信群，大家可以在这里谈论有关算法的问题。不过该群是禁止发推文的。需要进群的伙伴可以加我为好友，备注“从0打卡leetcode”，我拉你进群。
在公众号右下方有我的微信二维码。